 |
    |
The Edge-Set Encoding Revisited: On the Bias of a Direct Representation for Trees
Carsten Tzschoppe2, Franz Rothlauf1, and Hans-Josef Pesch2
1Department of Information Systems 1, University of Mannheim, 68131 Mannheim, Germany
rothlauf@uni-mannheim.de
2Department of Applied Mathematics, University of Bayreuth, 95440 Bayreuth, Germany
carsten.tzschoppe@gmx.de
hans-josef.pesch@uni-bayreuth.de
Abstract. The edge-set encoding is a direct tree representation which directly represents trees as sets of edges. There are two variants of the edge-set encoding: the edge-set encoding without heuristics, and the edge-set encoding with heuristics. An investigation into the bias of the edge-set encoding shows that the crossover operator of the edge-set encoding without heuristics is unbiased, that means it does not favor particular types of trees. In contrast, the crossover operator with heuristics is biased towards the simple minimum spanning tree (MST) and generates more likely trees that are MST-like. As a result, the performance of the edge-set encoding without heuristics does not depend on the structure of the optimal solution. Using the heuristic crossover operator results only in high genetic algorithm (GA) performance if the optimal solution of the problem is slightly different from the simple MST. However, if the optimal solution is not very similar to the simple MST a GA using the heuristic crossover operator fails and is not able to find the optimal solution. Therefore, it is recommended that the edge-set encoding with heuristics should only be used if it is known a priori that the optimal solution is very similar to the simple MST. If this is not known a priori, other unbiased search operators and representations should be used.
LNCS 3103, p. 258 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004